package java学习.leetcode.editor.cn;

import java.util.*;

/**
 * @author 刘世锦
 * 2022-10-11 22:25:55	 当前时间
 */
//给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k
// ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 
//
// 你返回所有和为 0 且不重复的三元组。 
//
// 注意：答案中不可以包含重复的三元组。 
//
// 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
//解释：
//nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
//nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
//nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
//不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
//注意，输出的顺序和三元组的顺序并不重要。
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,1,1]
//输出：[]
//解释：唯一可能的三元组和不为 0 。
// 
//
// 示例 3： 
//
// 
//输入：nums = [0,0,0]
//输出：[[0,0,0]]
//解释：唯一可能的三元组和为 0 。
// 
//
// 
//
// 提示： 
//
// 
// 3 <= nums.length <= 3000 
// -105 <= nums[i] <= 105 
// 
// Related Topics 数组 双指针 排序 
// 👍 5303 👎 0

public class 三数之和{
	public static void main(String[] args) {
		Solution solution = new 三数之和().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	/**
	 * 排序+双指针：为什么？因为官网是这样
	 * 三数之和： a=nums[i],b=nums[left],c=nums[right]
	 * @param nums
	 * @return
	 */
    public List<List<Integer>> threeSum1(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>> res = new ArrayList<>();
		for (int i = 0; i < nums.length; i++) {
			if (nums[i]>0){
//				排序之后，定是 小→大 ，那第一个都>0了，后面的必然>0, 三数之和就!=0了
				return res;
			}
			if (i>0&& nums[i]==nums[i-1]){ // 对 a = nums[i]去重
//				若  nums[i]==nums[i-1] 说明 现在a已经出现过一次了，现在a在中间：
//				   i-1 i
//				nums[1,1,2,3] // 此时就需要过滤掉，往后走
				continue;// 略过的意思
			}
			int left = i+1;
			int right = nums.length-1;
			while (left<right){
				int sum = nums[i]+nums[left]+nums[right];
				if (sum>0){
//					说明现在的数需要变小，right左移←
					right--;
				}else if (sum<0){
//					说明现在的数需要变大，left右移→
					left++;
				}else {
//					现在三数之和=0，开始记录到res中
					res.add(Arrays.asList(nums[i],nums[left],nums[right]));
					while (left<right&&nums[left]==nums[left+1]) {
						left++; // 对 b=nums[left] 去重，去掉重复值
					}
					while (left<right&&nums[right-1]==nums[right]) {
						right--; // 对 c=nums[right] 去重，去掉重复值
					}
					right--;
					left++;
				}
			}

		}

		return  res;
    }
	public List<List<Integer>> threeSum(int[] nums) {
    	Arrays.sort(nums);
		List<List<Integer>> list = new ArrayList<>();
		for (int i = 0; i < nums.length; i++) {
			if (nums[i]>0){
				return list;
			}
			if (i>0&&nums[i]==nums[i-1]){
//				对a去重
				continue;
			}
			int left = i+1;
			int right = nums.length-1;
			while (left<right){
//				判断三数之和：
				int sum = nums[i]+nums[left]+nums[right];
				if (sum>0){
					right--;
				}else if (sum<0){
					left++;
				}else{
					list.add(Arrays.asList(nums[i],nums[left],nums[right]));
					while (left<right&&nums[left]==nums[left+1]){
						left++;
					}
					while (left<right&& nums[right] == nums[right-1]){
						right--;
					}
					left++;
					right--;
				}
			}
		}
		return list;
	}


		public List<List<Integer>> threeSum3(int[] nums) {
		Arrays.sort(nums);
		Set<List<Integer>> lists = new HashSet<>();
		for (int i = 0; i < nums.length; i++) {
			int left = i + 1, right = nums.length - 1;
			while (left < right) {
				if (nums[left] + nums[right] + nums[i] == 0) {
					lists.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
					left++;
					right--;
				} else if (nums[i] + nums[left] + nums[right] < 0) {
					left++;
				} else {
					right--;
				}
			}
		}
		List<List<Integer>> list = new ArrayList<>(lists);
		return list;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
